home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / ddj0897.zip / DYN401.ZIP / class / btreenod.c < prev    next >
C/C++ Source or Header  |  1997-04-16  |  14KB  |  535 lines
  1.  
  2.  
  3. /*  Copyright (c) 1993-1996 Algorithms Corporation  */
  4. /*  All rights reserved.  */
  5.  
  6.  
  7.  
  8.  
  9. /*  This file automatically generated by dpp - do not edit  */
  10.  
  11. #define    DPP_STRATEGY    2
  12. #define    DPP_FASTWIDE    0
  13.  
  14.  
  15.  
  16. #line 18 "btreenod.d"
  17. #include <string.h> 
  18.  
  19. #define OBJECTS_PER_NODE 50 
  20.  
  21. #define MAX_DEPTH 10 
  22.  
  23.  
  24. #define MEMMOVE(a,b,c) memmove((void *)(a), (void *)(b), c) 
  25. #define MEMSET(a,b,c) memset((void *)(a), b, c) 
  26. #define MEMCPY(a,b,c) memcpy((void *)(a), (void *)(b), c) 
  27.  
  28. #define    CLASS    BTreeNode_c
  29. #define    ivType    BTreeNode_iv_t
  30.  
  31. #include "generics.h"
  32.  
  33. object    BTreeNode_c;
  34.  
  35.  
  36. #line 37 "btreenod.c"
  37. typedef struct  _BTreeNode_iv_t  {
  38.     int iUsed;
  39.     int iType;
  40.     object iKeys [ OBJECTS_PER_NODE ];
  41.     object iObjects [ OBJECTS_PER_NODE + 1 ];
  42.     object iBTree;
  43.     object iPrevious;
  44. }    BTreeNode_iv_t;
  45.  
  46.  
  47. #line 48 "btreenod.c"
  48. typedef struct  _BTreeNode_cv_t  {
  49.     object cData;
  50. }    BTreeNode_cv_t;
  51.  
  52. static    BTreeNode_cv_t    *BTreeNode_cv;
  53.  
  54.  
  55.  
  56. #line 44 "btreenod.d"
  57. cmeth objrtn BTreeNode_cm_gNewNode(object self, object btree, int type)
  58. { 
  59.     object obj = oSuper(BTreeNode_c, gNew, self)(self); 
  60.     accessIVsOf(obj); 
  61.     iv->iBTree = btree; 
  62.     iv->iType = type; 
  63.     if (!BTreeNode_cv->cData) 
  64.         BTreeNode_cv->cData = gNew(Constant); 
  65.     return obj; 
  66. } 
  67.  
  68. imeth objrtn BTreeNode_im_gDispose(object self)
  69. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  70.     int i; 
  71.     object n; 
  72.  
  73.     if (iv->iType == 1) { 
  74.         for (i=0 ; i < iv->iUsed ; ++i) { 
  75.             if (n = iv->iKeys[i]) 
  76.                 gDeepDispose(n); 
  77.             if (n = iv->iObjects[i]) 
  78.                 gDispose(n); 
  79.         } 
  80.         if (n = iv->iObjects[iv->iUsed]) 
  81.             gDispose(n); 
  82.     } 
  83.     return oSuper(BTreeNode_c, gDispose, self)(self); 
  84. } 
  85.  
  86. imeth objrtn BTreeNode_im_gDeepDispose(object self)
  87. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  88.     int i; 
  89.     object n; 
  90.  
  91.     for (i=0 ; i < iv->iUsed ; ++i) { 
  92.         if (n = iv->iKeys[i]) 
  93.             gDeepDispose(n); 
  94.         if (n = iv->iObjects[i]) 
  95.             gDeepDispose(n); 
  96.     } 
  97.     if (iv->iType == 1 && (n = iv->iObjects[iv->iUsed])) 
  98.         gDeepDispose(n); 
  99.     return oSuper(BTreeNode_c, gDispose, self)(self); 
  100. } 
  101.  
  102. static int bsearch2(ivType *iv, ifun cfun, object key, int *idx) 
  103. { 
  104.     int low = 0, high = iv->iUsed-1, mid, cond; 
  105.  
  106.     while (low <= high) { 
  107.         mid = (low + high) / 2; 
  108.         cond = cfun(key, iv->iKeys[mid]); 
  109.         if (cond < 0) 
  110.             high = mid - 1; 
  111.         else if (cond > 0) 
  112.             low = mid + 1; 
  113.         else 
  114.             break; 
  115.     } 
  116.     if (low <= high) { 
  117.         *idx = mid; 
  118.         return 1; 
  119.     } else { 
  120.         *idx = low; 
  121.         return 0; 
  122.     } 
  123. } 
  124.  
  125. imeth objrtn find(object self, ifun cfun, object key, object *foundKey)
  126. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  127.     int found, idx; 
  128.  
  129.     found = bsearch2(iv, cfun, key, &idx); 
  130.     if (iv->iType == 2) 
  131.         if (found) { 
  132.         if (foundKey) 
  133.             *foundKey = iv->iKeys[idx]; 
  134.         return iv->iObjects[idx]; 
  135.     } else 
  136.         return NULL; 
  137.     return find(iv->iObjects[found+idx], cfun, key, foundKey); 
  138. } 
  139.  
  140. imeth objrtn findFirst(object self, ifun cfun, object *foundKey)
  141. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  142.     if (iv->iType == 2) { 
  143.         if (foundKey) 
  144.             *foundKey = iv->iKeys[0]; 
  145.         return iv->iObjects[0]; 
  146.     } 
  147.     return findFirst(iv->iObjects[0], cfun, foundKey); 
  148. } 
  149.  
  150. imeth objrtn findLast(object self, ifun cfun, object *foundKey)
  151. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  152.     if (iv->iType == 2) { 
  153.         if (foundKey) 
  154.             *foundKey = iv->iKeys[iv->iUsed-1]; 
  155.         return iv->iObjects[iv->iUsed-1]; 
  156.     } 
  157.     return findLast(iv->iObjects[iv->iUsed], cfun, foundKey); 
  158. } 
  159.  
  160. imeth objrtn findGE(object self, ifun cfun, object key, object *foundKey)
  161. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  162.     int found, idx; 
  163.     object ret; 
  164.  
  165.     found = bsearch2(iv, cfun, key, &idx); 
  166.     if (iv->iType == 2) 
  167.         if (idx != iv->iUsed) { 
  168.         if (foundKey) 
  169.             *foundKey = iv->iKeys[idx]; 
  170.         return iv->iObjects[idx]; 
  171.     } else { 
  172.         if (foundKey) 
  173.             *foundKey = NULL; 
  174.         return NULL; 
  175.     } 
  176.     for (idx=idx+found ; idx <= iv->iUsed ; idx++) 
  177.         if (ret = findGE(iv->iObjects[idx], cfun, key, foundKey)) 
  178.         return ret; 
  179.     return NULL; 
  180. } 
  181.  
  182. imeth objrtn findGT(object self, ifun cfun, object key, object *foundKey)
  183. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  184.     int found, idx; 
  185.     object ret; 
  186.  
  187.     found = bsearch2(iv, cfun, key, &idx); 
  188.     if (found) 
  189.         idx++; 
  190.     if (iv->iType == 2) 
  191.         if (idx != iv->iUsed) { 
  192.         if (foundKey) 
  193.             *foundKey = iv->iKeys[idx]; 
  194.         return iv->iObjects[idx]; 
  195.     } else { 
  196.         if (foundKey) 
  197.             *foundKey = NULL; 
  198.         return NULL; 
  199.     } 
  200.     for ( ; idx <= iv->iUsed ; idx++) 
  201.         if (ret = findGT(iv->iObjects[idx], cfun, key, foundKey)) 
  202.         return ret; 
  203.     return NULL; 
  204. } 
  205.  
  206. imeth objrtn findLE(object self, ifun cfun, object key, object *foundKey)
  207. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  208.     int found, idx; 
  209.     object ret; 
  210.  
  211.     found = bsearch2(iv, cfun, key, &idx); 
  212.     if (iv->iType == 2) 
  213.         if (found) { 
  214.         if (foundKey) 
  215.             *foundKey = iv->iKeys[idx]; 
  216.         return iv->iObjects[idx]; 
  217.     } else if (idx) { 
  218.         if (foundKey) 
  219.             *foundKey = iv->iKeys[idx-1]; 
  220.         return iv->iObjects[idx-1]; 
  221.     } else { 
  222.         if (foundKey) 
  223.             *foundKey = NULL; 
  224.         return NULL; 
  225.     } 
  226.     for (idx=idx+found ; idx >= 0 ; idx--) 
  227.         if (ret = findLE(iv->iObjects[idx], cfun, key, foundKey)) 
  228.         return ret; 
  229.     return NULL; 
  230. } 
  231.  
  232. imeth objrtn findLT(object self, ifun cfun, object key, object *foundKey)
  233. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  234.     int idx; 
  235.     object ret; 
  236.  
  237.     bsearch2(iv, cfun, key, &idx); 
  238.     if (iv->iType == 2) 
  239.         if (idx) { 
  240.         if (foundKey) 
  241.             *foundKey = iv->iKeys[idx-1]; 
  242.         return iv->iObjects[idx-1]; 
  243.     } else { 
  244.         if (foundKey) 
  245.             *foundKey = NULL; 
  246.         return NULL; 
  247.     } 
  248.     for ( ; idx >= 0 ; idx--) 
  249.         if (ret = findLT(iv->iObjects[idx], cfun, key, foundKey)) 
  250.         return ret; 
  251.     return NULL; 
  252. } 
  253.  
  254. static void collapse(ivType *liv, object lo, int deep) 
  255. { 
  256.     object self = liv->iPrevious; 
  257.     ivType *iv = ivPtr(self); 
  258.     int idx; 
  259.  
  260.     if (iv->iUsed == 1) 
  261.         if (iv->iPrevious) { 
  262.         collapse(iv, liv->iPrevious, deep); 
  263.         return; 
  264.     } else if (iv->iType == 1) { 
  265.         if (deep) 
  266.             gDeepDispose(lo); 
  267.         else 
  268.             gDispose(lo); 
  269.         iv->iKeys[0] = gDeepDispose(iv->iKeys[0]); 
  270.         gSetTopNode(iv->iBTree, iv->iObjects[iv->iObjects[0] == lo]); 
  271.         iv->iObjects[0] = iv->iObjects[1] = NULL; 
  272.         iv->iUsed = 0; 
  273.         gDeepDispose(self); 
  274.         return; 
  275.     } 
  276.     for (idx=0 ; iv->iObjects[idx] != lo ; idx++); 
  277.     if (!idx) { 
  278.         gDeepDispose(iv->iKeys[0]); 
  279.         MEMMOVE(iv->iKeys, iv->iKeys+1, (iv->iUsed-1)*sizeof(object)); 
  280.         MEMMOVE(iv->iObjects, iv->iObjects+1, iv->iUsed*sizeof(object)); 
  281.     } else { 
  282.         gDeepDispose(iv->iKeys[idx-1]); 
  283.         MEMMOVE(iv->iKeys+idx-1, iv->iKeys+idx, (iv->iUsed-idx)*sizeof(object)); 
  284.         MEMMOVE(iv->iObjects+idx, iv->iObjects+idx+1, (iv->iUsed-idx)*sizeof(object)); 
  285.     } 
  286.     iv->iKeys[iv->iUsed-1] = iv->iObjects[iv->iUsed] = NULL; 
  287.     iv->iUsed--; 
  288.     if (deep) 
  289.         gDeepDispose(lo); 
  290.     else 
  291.         gDispose(lo); 
  292. } 
  293.  
  294. imeth objrtn delete(object self, ifun cfun, object key, int deep, object prev)
  295. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  296.     int found, idx; 
  297.     object res; 
  298.  
  299.     found = bsearch2(iv, cfun, key, &idx); 
  300.     if (iv->iType == 2) { 
  301.         if (!found) 
  302.             return NULL; 
  303.         if (iv->iUsed == 1 && prev) { 
  304.             iv->iPrevious = prev; 
  305.             collapse(iv, self, deep); 
  306.         } else { 
  307.             int n = iv->iUsed - idx - 1; 
  308.             if (deep) { 
  309.                 gDeepDispose(iv->iKeys[idx]); 
  310.                 gDeepDispose(iv->iObjects[idx]); 
  311.             } 
  312.             MEMMOVE(iv->iKeys+idx, iv->iKeys+idx+1, n*sizeof(object)); 
  313.             MEMMOVE(iv->iObjects+idx, iv->iObjects+idx+1, n*sizeof(object)); 
  314.             iv->iUsed--; 
  315.             iv->iKeys[iv->iUsed] = iv->iObjects[iv->iUsed] = NULL; 
  316.         } 
  317.         return self; 
  318.     } 
  319.     iv->iPrevious = prev; 
  320.     res = delete(iv->iObjects[found+idx], cfun, key, deep, self); 
  321.     iv->iPrevious = NULL; 
  322.     return res; 
  323. } 
  324.  
  325. static object split(object lo, ivType *left, ifun cfun) 
  326. { 
  327.     object to, ro, ret; 
  328.     ivType *right, *top; 
  329.     int lhalf, rhalf; 
  330.  
  331.     ro = gNewNode(CLASS, left->iBTree, left->iType); 
  332.     right = ivPtr(ro); 
  333.     if (left->iType == 2) { 
  334.         lhalf = left->iUsed / 2; 
  335.         rhalf = left->iUsed - lhalf; 
  336.         MEMCPY(right->iKeys, left->iKeys+lhalf, rhalf*sizeof(object)); 
  337.         MEMSET(left->iKeys+lhalf, 0, rhalf*sizeof(object)); 
  338.         left->iUsed = lhalf; 
  339.         right->iUsed = rhalf; 
  340.         MEMCPY(right->iObjects, left->iObjects+lhalf, rhalf*sizeof(object)); 
  341.         MEMSET(left->iObjects+lhalf, 0, rhalf*sizeof(object)); 
  342.     } else { 
  343.         lhalf = left->iUsed / 2; 
  344.         rhalf = left->iUsed - lhalf - 1; 
  345.         MEMCPY(right->iKeys, left->iKeys+lhalf+1, rhalf*sizeof(object)); 
  346.         MEMSET(left->iKeys+lhalf+1, 0, rhalf*sizeof(object)); 
  347.         left->iUsed = lhalf; 
  348.         right->iUsed = rhalf; 
  349.         MEMCPY(right->iObjects, left->iObjects+lhalf+1, (rhalf+1)*sizeof(object)); 
  350.         MEMSET(left->iObjects+lhalf+1, 0, (rhalf+1)*sizeof(object)); 
  351.     } 
  352.  
  353.     if (!(ret=to=left->iPrevious)) { 
  354.         ret = to = gNewNode(CLASS, left->iBTree, 1); 
  355.         gSetTopNode(left->iBTree, to); 
  356.         top = ivPtr(to); 
  357.         top->iKeys[0] = gDeepCopy(right->iKeys[0]); 
  358.         top->iObjects[0] = lo; 
  359.         top->iObjects[1] = ro; 
  360.         top->iUsed = 1; 
  361.     } else { 
  362.         int found, idx, n; 
  363.  
  364.         top = ivPtr(to); 
  365.         if (top->iUsed == OBJECTS_PER_NODE) { 
  366.             ret = to = split(to, top, cfun); 
  367.             top = ivPtr(to); 
  368.             found = bsearch2(top, cfun, right->iKeys[0], &idx); 
  369.             to = top->iObjects[found+idx]; 
  370.             top = ivPtr(to); 
  371.         } 
  372.         found = bsearch2(top, cfun, right->iKeys[0], &idx); 
  373.         if (found) 
  374.             gError(Dynace, "BTreeNode error"); 
  375.         n = top->iUsed - idx; 
  376.         if (n) { 
  377.             MEMMOVE(top->iKeys+idx+1, top->iKeys+idx, n*sizeof(object)); 
  378.             MEMMOVE(top->iObjects+idx+2, top->iObjects+idx+1, n*sizeof(object)); 
  379.         } 
  380.         top->iKeys[idx] = gDeepCopy(right->iKeys[0]); 
  381.         top->iObjects[idx+1] = ro; 
  382.         top->iUsed++; 
  383.     } 
  384.  
  385.     return ret; 
  386. } 
  387.  
  388. #line 385 "btreenod.d"
  389. #define DATA data ? data : BTreeNode_cv->cData 
  390.  
  391. imeth objrtn add(object self, ifun cfun, object key, object data, int replace, int *replaced, object prev, object *old)
  392. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  393.     int found, idx; 
  394.     object tmp, ret; 
  395.  
  396.     found = bsearch2(iv, cfun, key, &idx); 
  397.     if (iv->iType == 1) { 
  398.         iv->iPrevious = prev; 
  399.         ret = add(iv->iObjects[found+idx], cfun, key, DATA, replace, replaced, self, old); 
  400.         iv->iPrevious = NULL; 
  401.         return ret; 
  402.     } 
  403.  
  404.     if (found) 
  405.         if (replace) { 
  406.         *old = iv->iObjects[idx]; 
  407.         iv->iObjects[idx] = DATA; 
  408.         *replaced = 2; 
  409.         return self; 
  410.     } else { 
  411.         *replaced = 0; 
  412.         return self; 
  413.     } 
  414.  
  415.  
  416.  
  417.     if (iv->iUsed == OBJECTS_PER_NODE) { 
  418.         iv->iPrevious = prev; 
  419.         tmp = split(self, iv, cfun); 
  420.         iv->iPrevious = NULL; 
  421.         return add(tmp, cfun, key, DATA, replace, replaced, NULL, old); 
  422.     } 
  423.  
  424.     if (idx != iv->iUsed) { 
  425.         int n = iv->iUsed - idx; 
  426.         MEMMOVE(iv->iKeys+idx+1, iv->iKeys+idx, n*sizeof(object)); 
  427.         MEMMOVE(iv->iObjects+idx+1, iv->iObjects+idx, n*sizeof(object)); 
  428.     } 
  429.     iv->iKeys[idx] = key; 
  430.     iv->iObjects[idx] = DATA; 
  431.     iv->iUsed++; 
  432.     *replaced = 1; 
  433.     return self; 
  434. } 
  435.  
  436. imeth objrtn BTreeNode_im_gPrint(object self, object stream)
  437. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  438.     int i, n; 
  439.  
  440.     gPrintValue(self, stream); 
  441.     gPuts(stream, "\n------------------------------------------------------------\n"); 
  442.     if (iv->iType == 1) { 
  443.         n = iv->iUsed + 1; 
  444.         for (i=0 ; i < n ; i++) 
  445.             gPrint(iv->iObjects[i], stream); 
  446.     } 
  447.     return self; 
  448. } 
  449.  
  450. imeth objrtn BTreeNode_im_gPrintValue(object self, object stream)
  451. { BTreeNode_iv_t *iv = GetIVs(BTreeNode, self);
  452.     int i, n; 
  453.     object t; 
  454.  
  455.     vPrintf(stream, "BTree %8.8lx, %s node %8.8lx, %d used\n", iv->iBTree, iv->iType == 1 ? "Intermediate" : "Leaf", self, iv->iUsed); 
  456.     if (!iv->iBTree) 
  457.         vPrintf(stream, "ERROR: iBTRee not set\n"); 
  458.     if (iv->iPrevious) 
  459.         vPrintf(stream, "ERROR: iPrevious set\n"); 
  460.     for (i=0 ; i < iv->iUsed ; i++) { 
  461.         t = gStringRepValue(iv->iKeys[i]); 
  462.         vPrintf(stream, "%s  ", gStringValue(t)); 
  463.         gDispose(t); 
  464.     } 
  465.     for ( ; i < OBJECTS_PER_NODE ; i++) 
  466.         if (iv->iKeys[i]) 
  467.         vPrintf(stream, "\nERROR:  iKeys[%d] has an unexpected value.\n", i); 
  468.     gPuts(stream, "\n"); 
  469.     if (iv->iType == 1) { 
  470.         n = iv->iUsed + 1; 
  471.         for (i=0 ; i < n ; i++) 
  472.             vPrintf(stream, "%8.8lx  ", iv->iObjects[i]); 
  473.     } else 
  474.         for (i=0 ; i < iv->iUsed ; i++) { 
  475.         t = gStringRepValue(iv->iObjects[i]); 
  476.         vPrintf(stream, "%s  ", gStringValue(t)); 
  477.         gDispose(t); 
  478.     } 
  479.     for ( ; i <= OBJECTS_PER_NODE ; i++) 
  480.         if (iv->iObjects[i]) 
  481.         vPrintf(stream, "\nERROR:  iObjects[%d] has an unexpected value.\n", i); 
  482.     gPuts(stream, "\n"); 
  483.     return self; 
  484. } 
  485.  
  486.  
  487. #line 488 "btreenod.c"
  488.  
  489. objrtn    BTreeNode_initialize(void)
  490. {
  491.     static  CRITICALSECTION  cs;
  492.     static  int volatile once = 0;
  493.  
  494.     ENTERCRITICALSECTION(_CI_CS_);
  495.     if (!once) {
  496.         INITIALIZECRITICALSECTION(cs);
  497.         once = 1;
  498.     }
  499.     LEAVECRITICALSECTION(_CI_CS_);
  500.  
  501.     ENTERCRITICALSECTION(cs);
  502.  
  503.     if (BTreeNode_c) {
  504.         LEAVECRITICALSECTION(cs);
  505.         return BTreeNode_c;
  506.     }
  507.     INHIBIT_THREADER;
  508.     BTreeNode_c = gNewClass(Class, "BTreeNode", sizeof(BTreeNode_iv_t), sizeof(BTreeNode_cv_t), END);
  509.     cMethodFor(BTreeNode, gNewNode, BTreeNode_cm_gNewNode);
  510.     iMethodFor(BTreeNode, gFindBTNGE, findGE);
  511.     iMethodFor(BTreeNode, gFindBTNLT, findLT);
  512.     iMethodFor(BTreeNode, gFindBTNFirst, findFirst);
  513.     iMethodFor(BTreeNode, gFindBTNLE, findLE);
  514.     iMethodFor(BTreeNode, gPrint, BTreeNode_im_gPrint);
  515.     iMethodFor(BTreeNode, gAddBTreeNode, add);
  516.     iMethodFor(BTreeNode, gFindBTNEQ, find);
  517.     iMethodFor(BTreeNode, gFindBTNLast, findLast);
  518.     iMethodFor(BTreeNode, gDispose, BTreeNode_im_gDispose);
  519.     iMethodFor(BTreeNode, gFindBTNGT, findGT);
  520.     iMethodFor(BTreeNode, gDeleteBTNode, delete);
  521.     iMethodFor(BTreeNode, gDeepDispose, BTreeNode_im_gDeepDispose);
  522.     iMethodFor(BTreeNode, gPrintValue, BTreeNode_im_gPrintValue);
  523.  
  524.     BTreeNode_cv = GetCVs(BTreeNode);
  525.  
  526.     ENABLE_THREADER;
  527.  
  528.     LEAVECRITICALSECTION(cs);
  529.  
  530.     return BTreeNode_c;
  531. }
  532.  
  533.  
  534.  
  535.